<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<link rel="stylesheet" type="text/css" href="newstyle.css">
<meta http-equiv="Content-Type" content="text/html;
  charset=iso-8859-1">
<title>Reverse Polish Notation</title>
</head>
<body>

<div id="top">
<h2>Reverse Polish Notation</h2>
</div>
<div id="trail">
<p><a href="http://www-stone.ch.cam.ac.uk/">Home</a>
 -> <a href="http://www-stone.ch.cam.ac.uk/programs.html">Programs</a>
 -> <a href="index.html">RRF</a>
 -> Reverse Polish Notation</p>
</div>

<!-- Index starts here -->
<div id="index">
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/index.html">Home</a></p>
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/personal/personal.html">Personal information</a></p>
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/programs.html">Computer programs</a></p>
<p class="indexentry"><a
href="http://www.ch.cam.ac.uk/staff/ajs.html">Research details</a></p>
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/personal/timf.html">The Theory of Intermolecular Forces</a></p>
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/personal/bibliography.html">Publications</a></p>
<p class="indexentry"><a href="http://www-stone.ch.cam.ac.uk/personal/supplementary.html">
Supplementary material for published papers</a></p>
</div>
<!-- Index ends here -->


<div id="content">


<p>Reverse Polish Notation is a way of expressing arithmetic
expressions that avoids the use of brackets to define priorities for
evaluation of operators.  In ordinary notation, one might write</p>
<p>(3 + 5) * (7 &#8211; 2)</p>
<p>and the brackets tell us that we have to add 3 to 5, then subtract
2 from 7, and multiply the two results together. In RPN, the numbers
and operators are listed one after another, and an operator always
acts on the most recent numbers in the list. The numbers can be
thought of as forming a stack, like a pile of plates. The most recent
number goes on the top of the stack. An operator takes the appropriate
number of arguments from the top of the stack and replaces them by the
result of the operation.</p>

<p>In this notation the above expression would be</p>
<p>3 5 + 7 2 &#8211; *</p>
<p>Reading from left to right, this is interpreted as follows:</p>
<ul>
<li>Push 3 onto the stack. </li>
<li>Push 5 onto the stack. Reading from the bottom, the stack now
contains (3, 5). </li>
<li>Apply the + operation: take the top two numbers off the stack, add
them together, and put the result back on the stack. The stack now
contains just the number 8.</li>
<li>Push 7 onto the stack. </li>
<li>Push 2 onto the stack. It now contains (8, 7, 2). </li>
<li>Apply the &#8211; operation: take the top two numbers off the stack,
subtract the top one from the one below, and put the result back on
the stack. The stack now contains (8, 5).</li>
<li>Apply the * operation: take the top two numbers off the stack,
multiply them together, and put the result back on the stack. The
stack now contains just the number 40.</li>
</ul>
</div>
<!--		Ends Here			-->

<div id="foot">
<!--#config timefmt="%d %B, %Y" -->
<p>This page is maintained by
<a href="mailto:ajs1%40cam.ac.uk">Anthony Stone</a>,
and was last updated on <!--#flastmod file="rpn.html" -->. </p>
</div>
<div id="w3valid">
<p>
    <a href="http://validator.w3.org/check?uri=referer"><img
      src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional" height="31" width="88"></a>
  </p>
</div>
</body>
</html>
